/**
 * @file
 * @author Nikhil S. Ketkar
 * An optimized data structure for isomorphism type problems. 
 * One way of thinking about this data structure is that it stores all 
 * possible "expansions" from a given vertex. This is exactly the kind of access 
 * required for isomorphism type of problems.
 */
#ifndef EXPANSION_GRAPH_H
#define EXPANSION_GRAPH_H

#include <iostream>
#include <map>
#include <set>

/**
 * An optimized data structure for isomorphism type problems.
 * This data structure is that it stores all possible "expansions" 
 * from a given vertex. This is exactly the kind of access 
 * required for isomorphism type of problems.
 */
template<class V, class E>
class ExpansionGraph
{
 public:
  bool add_vertex(V* v);
  bool add_edge(E *e, V* v1, V* v2);

  void print();

  bool get_expansions(V *v, std::map<E*, V*> *result);
  bool get_expansions_subset(V *v, std::set<E*> *edge_set, std::map<E*, V*> *result);

  V* get_edge1(E *given);
  V* get_edge2(E *given);

 private:
  std::map< V*, std::map<E*, V*> > expansions;
  std::map< E*, V*> edge1;
  std::map< E*, V*> edge2;
};

/**
 * Prints the instance, for debugging.
 */
template<class V, class E>
  void ExpansionGraph<V,E>::print()
{  
  std::cerr << "Graph:\n";
  std::cerr << "Expansions:\n";
  for(typename std::map< V*, std::map<E*, V*> >::iterator i = expansions.begin();
      i != expansions.end();
      i++)
    {
      for(typename std::map<E*, V*>::iterator j = (i->second).begin();
          j != (i->second).end();
          j++)
        {
          (i->first)->print();
          (j->first)->print();
          (j->second)->print();
        }
    }
}

/**
 * Add a new vertex, returns false if already present.
 * @param[in] v Vertex to be added.
 * @return @c false if such a vertex is already present, @c true otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::add_vertex(V *v)
{
  // Check if the vertex is already present
  if(expansions.find(v) == expansions.end())
    {
      // Create a new set for expansions and put it as the value for that vertex 
      // index
      std::map<E*, V*> curr_expansions;
      expansions[v] = curr_expansions;
      return true;
    }
  else
    return false;
}

/**
 * Add a new edge on two previously added vertices.
 * @param[in] e Edge to be added.
 * @param[in] v1 A vertex corresponding to the edge.
 * @param[in] v2 The other vertex.
 * @return @c true if both the vertices are already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::add_edge(E *e, V* v1, V* v2)
{
  // Check if both the vertices have been introduced previously
  if((expansions.find(v1) != expansions.end())  
     && (expansions.find(v2) != expansions.end()))
    {
      // Add expansion for v1 on edge e going to vertex v2
      (expansions[v1])[e] = v2;

      // Add expansion for v2 on edge e going to vertex v1
      (expansions[v2])[e] = v1;

      edge1[e] = v1; 
      edge2[e] = v2;

      return true;
    }
    else
      return false;
}

template<class V, class E>
  V* ExpansionGraph<V, E>::get_edge1(E *given)
{
  return edge1[given];
}

template<class V, class E>
  V* ExpansionGraph<V, E>::get_edge2(E * given)
{
  return edge2[given];
}

/**
 * Get expansions on a vertex, return false if none exist.
 * @param[in] v Vertex for which expansions are requested.
 * @param[out] result Result location to write to.
 * @return @c true if the vertex is already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::get_expansions(V *v,  std::map<E*, V*> *result)
{
  // Check if vertex is present
  if(expansions.find(v) != expansions.end())
    {
      // Copy the expansions set on to the result
      *result = expansions[v];
      return true;
    }
  else
    return false;
}

/**
 * Get expansions on a vertex, constrained by given set of edges.
 * If an edge is not in the set, the expansion through that edge is not present 
 * in the result.
 * @param[in] v Vertex for which expansions are requested.
 * @param[in] edge_set Edge set that constrains the expansions.
 * @param[out] result Result location to write to.
 * @return @c true if the vertex is already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::get_expansions_subset
  (
   V *v, 
   std::set<E*> *edge_set, 
   std::map<E*, V*> *result  
   )
{
  // Check if the vertex is present
  if(expansions.find(v) != expansions.end())
    {
      // Copy the expansions set on to the result
      *result = expansions[v];
      
      // Iterate over the expansions
      for(typename std::map<E*, V*>::iterator i = result->begin();
          i != result->end();)
        // Check if the edge on which the current expansion is based
        // is present in the given edge_set
        if(edge_set->find(i->first) == edge_set->end())
          // Erase the expansion if the edge is absent 
          result->erase(i++);
        else
          i++;
      
      return true;
    }
  else
    return false;
}
#endif // EXPANSION_GRAPH_H

